﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iterator>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int m, n;
    vector<vector<int>> exist;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (exist[i][j] != -1)//证明该位置已经搜索过，直接返回
            return exist[i][j];

        int len = 1;//从该位置开始的最长递增路径
        for (int k = 0; k < 4; ++k)
        {
            int newi = i + dx[k];
            int newj = j + dy[k];

            if (newi >= 0 && newi < m && newj >= 0 && newj < n && matrix[newi][newj] > matrix[i][j])
            {
                len = max(len, dfs(matrix, newi, newj) + 1);//接上下左右四个方向最大的递增路径
            }
        }

        exist[i][j] = len;//采用记忆化搜索可以节省一些运行时间
        return len;
    }
    int solve(vector<vector<int>>& matrix)
    {
        m = matrix.size();
        n = matrix[0].size();
        int result = 1;
        exist.assign(m, vector<int>(n, -1));
        for (int i = 0; i < m; ++i)//注意是没有规定起点的，所以是如何起点的最长递增路径
        {
            for (int j = 0; j < n; ++j)
            {
                result = max(result, dfs(matrix, i, j));
            }
        }
        return result;
    }
};

/*
给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 
你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。
并输出这条最长路径的长度。
这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围：
1≤n,m≤1000，0≤matrix[i][j]≤1000
进阶：空间复杂度O(nm) ，时间复杂度O(nm)
例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，
其中的一条最长递增路径如下图所示：

示例1
输入：
[[1,2,3],[4,5,6],[7,8,9]]
返回值：
5
说明：
1->2->3->6->9即可。当然这种递增路径不是唯一的。
*/

